home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / MCASM.RAR / MC_ASM.EXE / WROX_ASM / CH12 / COMMON / MAPPER2.H < prev    next >
C/C++ Source or Header  |  1994-09-24  |  6KB  |  139 lines
  1. #ifndef mapper2_h
  2. #define mapper2_h
  3. #include "palette.h"
  4. #include "mapper.h"
  5.  
  6. /*
  7.  * Map a TrueColor image into given palette
  8.  * Big part of code and ideas were taken
  9.  * from the  Independent JPEG Group's software.
  10.  *              ( see the accompanying README file).
  11.  * E.Podvoysky from ^Z for WROX press book
  12.  */
  13.  
  14.  
  15. /* see palette.h - first part of task */
  16.  
  17. /* E.P. - I do not re-use histogram space, because I split class.
  18.  * so in mapper cache we may have 1-byte cells
  19.  *  (but using only 255 colors, not 256.)
  20.  *
  21.  * We re-use the histogram space as an "inverse color map", essentially a
  22.  * cache for the results of nearest-color searches.  All colors within a
  23.  * histogram cell will be mapped to the same colormap entry, namely the one
  24.  * closest to the cell's center.  This may not be quite the closest entry to
  25.  * the actual input color, but it's almost as good.  A zero in the cache
  26.  * indicates we haven't found the nearest color for that cell yet; the array
  27.  * is cleared to zeroes before starting the mapping pass.  When we find the
  28.  * nearest color for a cell, its colormap index plus one is recorded in the
  29.  * cache for future use.  The pass2 scanning routines call fill_inverse_cmap
  30.  * when they need to use an unfilled entry in the cache.
  31.  *
  32.  * Our method of efficiently finding nearest colors is based on the "locally
  33.  * sorted search" idea described by Heckbert and on the incremental distance
  34.  * calculation described by Spencer W. Thomas in chapter III.1 of Graphics
  35.  * Gems II (James Arvo, ed.  Academic Press, 1991).  Thomas points out that
  36.  * the distances from a given colormap entry to each cell of the histogram can
  37.  * be computed quickly using an incremental method: the differences between
  38.  * distances to adjacent cells themselves differ by a constant.  This allows a
  39.  * fairly fast implementation of the "brute force" approach of computing the
  40.  * distance from every colormap entry to every histogram cell.  Unfortunately,
  41.  * it needs a work array to hold the best-distance-so-far for each histogram
  42.  * cell (because the inner loop has to be over cells, not colormap entries).
  43.  * The work array elements have to be INT32s, so the work array would need
  44.  * 256Kb at our recommended precision.  This is not feasible in DOS machines.
  45.  * Another disadvantage of the brute force approach is that it computes
  46.  * distances to every cell of the cubical histogram.  When working with YCbCr
  47.  * input, only about a quarter of the cube represents realizable colors, so
  48.  * many of the cells will never be used and filling them is wasted effort.
  49.  *
  50.  * To get around these problems, we apply Thomas' method to compute the
  51.  * nearest colors for only the cells within a small subbox of the histogram.
  52.  * The work array need be only as big as the subbox, so the memory usage
  53.  * problem is solved.  A subbox is processed only when some cell in it is
  54.  * referenced by the pass2 routines, so we will never bother with cells far
  55.  * outside the realizable color volume.  An additional advantage of this
  56.  * approach is that we can apply Heckbert's locality criterion to quickly
  57.  * eliminate colormap entries that are far away from the subbox; typically
  58.  * three-fourths of the colormap entries are rejected by Heckbert's criterion,
  59.  * and we need not compute their distances to individual cells in the subbox.
  60.  * The speed of this approach is heavily influenced by the subbox size: too
  61.  * small means too much overhead, too big loses because Heckbert's criterion
  62.  * can't eliminate as many colormap entries.  Empirically the best subbox
  63.  * size seems to be about 1/512th of the histogram (1/8th in each direction).
  64.  *
  65.  * Thomas' article also describes a refined method which is asymptotically
  66.  * faster than the brute-force method, but it is also far more complex and
  67.  * cannot efficiently be applied to small subboxes.  It is therefore not
  68.  * useful for programs intended to be portable to DOS machines.  On machines
  69.  * with plenty of memory, filling the whole histogram in one shot with Thomas'
  70.  * refined method might be faster than the present code --- but then again,
  71.  * it might not be any faster, and it's certainly more complicated.
  72.  */
  73.  
  74. #define MAP_R_BITS  HIST_R_BITS    /* bits of precision in R map */
  75. #define MAP_G_BITS  HIST_G_BITS    /* bits of precision in G map */
  76. #define MAP_B_BITS  HIST_B_BITS    /* bits of precision in B map */
  77.  
  78.  
  79. #define MAP_G_ELEMS  (1<<MAP_G_BITS) /* # of elements along histogram axes */
  80. #define MAP_R_ELEMS  (1<<MAP_R_BITS)
  81. #define MAP_B_ELEMS  (1<<MAP_B_BITS)
  82.  
  83. #define MAP_G_SHIFT  (8 - MAP_G_BITS)
  84. #define MAP_R_SHIFT  (8 - MAP_R_BITS)
  85. #define MAP_B_SHIFT  (8 - MAP_B_BITS)
  86.  
  87.  
  88. #define BOX_R_LOG  (MAP_R_BITS-3) /* log2(map cells in update box, R axes) */
  89. #define BOX_G_LOG  (MAP_G_BITS-3) /* log2(map cells in update box, G axes) */
  90. #define BOX_B_LOG  (MAP_B_BITS-3) /* log2(map cells in update box, C axes) */
  91.  
  92. #define BOX_R_ELEMS  (1<<BOX_R_LOG) /* # of map cells in update box */
  93. #define BOX_G_ELEMS  (1<<BOX_G_LOG)
  94. #define BOX_B_ELEMS  (1<<BOX_B_LOG)
  95.  
  96. #define BOX_R_SHIFT  (R_SHIFT + BOX_R_LOG)
  97. #define BOX_G_SHIFT  (G_SHIFT + BOX_G_LOG)
  98. #define BOX_B_SHIFT  (B_SHIFT + BOX_B_LOG)
  99.  
  100. #ifdef INT_MAP_CELL
  101.   typedef int mapcell;        /* color map cell */
  102. #else
  103.   typedef BYTE mapcell;        /* color map cell */
  104. #endif
  105.  
  106.  
  107. typedef mapcell far *mapptr;    /* for pointers to map cells */
  108. typedef mapcell map1d[MAP_B_ELEMS]; /* typedefs for the array */
  109. typedef map1d far * map2d;    /* type for the R-level pointers */
  110. typedef map2d *map3d;         /* typedefs for the array */
  111.  
  112.  
  113.     // no dithering, pre-selected colors
  114. class color_mapper_palette : public color_mapper {
  115. protected:
  116.     int map_r_elements; // internal use
  117.     // map3d map;    /* pointer to the map */
  118.     mapptr *map;
  119.     int find_nearby_colors (int minc0, int minc1, int minc2,BYTE colorlist[]);
  120.     void find_best_colors (int minc0, int minc1, int minc2,
  121.           int numcolors, BYTE colorlist[], BYTE bestcolor[]);
  122.     void fill_inverse_cmap (int c0, int c1, int c2);
  123.     virtual int initmap();
  124.  
  125. public:
  126.     color_mapper_palette(int colors_,int width_,BGRpalette colormap);
  127.     virtual ~color_mapper_palette();
  128.     virtual void process_line (BYTE *R, BYTE *G, BYTE *B, BYTE *out_line);
  129. };
  130.  
  131. class color_mapper_palette_dith : public color_mapper_palette {
  132. public:
  133.     color_mapper_palette_dith(int colors_,int width_,BGRpalette colormap);
  134.     virtual void process_line(BYTE *R, BYTE *G, BYTE *B, BYTE *out_line);
  135. };
  136.  
  137.  
  138. #endif
  139.